In the context of online advertising, behavioral targeting refers to the ability, through the use of anonymous data, to deliver advertisements to consumers based on their recent behavior. In this kind of advertisement model, advertisers review and buy a user segment to which they deliver their advertisements. For example, a video game advertiser may be interested in a user segment corresponding to users that have queried for “Xbox games” and/or have visited www.xbox.com, and so forth.
More formally, a user segment in a behavioral targeting system is defined as some user conditions met relative to some attributes, wherein each attribute represents the behavior of a set of users, such as the queries they have searched, or some set of URLs they have visited. There are several types of attributes; e.g., the URL pattern attribute represents the URLs the users visit, the query attribute represents the queries the users search in the search engine, the URL domain attribute represents the URL domain the users visit, and the product and service attribute represents the product and/or the service the users consume.
Attribute expansion tools have been developed to help advertisers define reasonably good user segments. With these expansion tools, advertisers can reach more users by expanding the set of users that meet certain attributes. The core functionality of these tools is to expand a set of attributes according to the original attributes provided by the advertiser.
The simplest way to do such an expansion is to write a separate algorithm for each special type of attribute expansion, e.g. an algorithm for expanding the query attribute to the URL pattern attribute. However, if there are N types of attributes, this technique requires writing N*N different expansion algorithms to meet the different expansion requirements.